/*
 * @lc app=leetcode.cn id=111 lang=javascript
 *
 * [111] 二叉树的最小深度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
//深度优先遍历
// var minDepth = function (root) {
//     if (root == null) {
//         return 0;
//         //递归到null的节点，返回高度0
//     }
//     if (root.left && root.right) {
//         // 左右子树都存在，当前节点的高度1+左右子树递归结果的较小值
//         return 1 + Math.min(minDepth(root.left), minDepth(root.right));
//     } else if (root.left) {
//         return 1 + minDepth(root.left);
//     } else if (root.right) {
//         return 1 + minDepth(root.right);
//     } else {
//         return 1;
//     }
// };

//广度优先遍历
var minDepth = function(root) {
    if(root == null) {
        return 0;
    }
    let queue = [];
    queue.push(root);//根节点先入列
    let Depth = 1;//当前节点树的深度
    while(queue.length) {
        let nowlength = queue.length;
        for(let i =0;i<nowlength;i++) {
            let pre = queue.shift();//当前节点出列
            if(pre.left == null && pre.right == null){
                return Depth;
                //若当前节点没有左右子节点，则返回当前树的深度
            }
            if(pre.left) queue.push(pre.left);
            if(pre.right) queue.push(pre.right);
            //相当于每层的节点都放入队列，每层的节点数则是新队列的长度
        }
        Depth++;
        //一层遍历完没有return,则深度加1
    }
}
// @lc code=end